/*
 * @(#)SellersFunction.java
 *
 * Revision:
 * Author                                         Date           
 * --------------------------------------------   ------------   
 * Ana Emilia Victor Barbosa Coutinho             25/06/2012    
 */
package br.edu.ufcg.splab.techniques.reduction.functions.similarity;

import java.text.DecimalFormat;

import br.edu.ufcg.splab.core.InterfaceEdge;
import br.edu.ufcg.splab.generator.TestCase;



public class SellersFunction implements DistanceFunction {

	/**
	 * Retrieve the similarity (number of repeated elements) in two specified paths.
	 * 
	 * @param path1 first test case.
	 * @param path2 second test case.
	 * @return similarity's value between the two paths. 
	 */
	public double getSimilarity(TestCase path1, TestCase path2){
		return getSellersDistance(path1, path2);
	}
	
	/**
     * Provide a string representation of the similarity function to be written.
     * @return The string representation of the similarity function.
     */
	public String getFunctionName(){
		return "Sel";
	}
	protected static final String TAB = "	";
	protected static final String EOL = System.getProperty("line.separator");

	/*
	 * The algorithm proposed by Sellers [Sellers 1980] aims to make a search for a string
	 * in another string with at most k operations difference. That is, its proposal is
	 * to determine whether a string is A sub-chain of another string B with at most k
	 * operations difference.
	 * 
	 * Sellers, P. H. (1980). The theory and computation of evolutionary distances: Pattern recognition. 
	 * J. Algorithms, 1(4):359-373.
	 */
	private double getSellersDistance(TestCase sequence1, TestCase sequence2) {
		int firstSequence = sequence1.getTestCase().size(); //Nodes sequence
		int secondSequence = sequence2.getTestCase().size();  
		double[][] distanceMatrix = new double[firstSequence+1][secondSequence+1]; //ranges from [0] to [size], thus size +1

		//The technique considers the labels in the nodes, since it is used for an Activity Diagram
		// The first columns and rows (i = 0 and j = 0) are for default values. (standard configuration of the algorithm) 
		for (int i = 0; i <= firstSequence; i++) {
			distanceMatrix[i][0] = (double)i; 
		}
		for (int j = 0; j <= secondSequence; j++) {
			distanceMatrix[0][j] = (double)0.00; 
		}
		
		for (int j = 1; j <= secondSequence; j++) { //columns
			for (int i = 1; i <= firstSequence; i++) { //rows
				InterfaceEdge node1 = sequence1.getTestCase().get(i-1);
				InterfaceEdge node2 = sequence2.getTestCase().get(j-1);
				if(node1.toString().equals(node2.toString())){
					distanceMatrix[i][j] = distanceMatrix[i-1][j-1];
				}else{
					distanceMatrix[i][j] = Math.min(Math.min(distanceMatrix[i-1][j]+1.0, distanceMatrix[i][j-1]+1.0),distanceMatrix[i-1][j-1]+1.0);
				}
			}
		}
		
		DecimalFormat fmt = new DecimalFormat("##,##0.000");
		String str = "";
		for (int line = 0; line < distanceMatrix.length; line++) {
//		 	str = str + (line + 1) + TAB;
//		 	for (int i = 0; i <= line; i++) {
//		 		str = str + TAB;
//			}
			for (int column = 0; column < distanceMatrix.length; column++) {
				str = str + (fmt.format(distanceMatrix[line][column])) + TAB;
			}
			str = str + EOL;			
		}
		System.out.println(str);
		
		
		if(firstSequence > secondSequence){
			return (double) (1 - (distanceMatrix[firstSequence][secondSequence]/(double)firstSequence));	
		}else {
			return (double) (1 - (distanceMatrix[firstSequence][secondSequence]/(double)secondSequence));
		}
	}
		
}
